1. Field of the Invention
The present invention relates generally to systems for half-toning the outputs of printers and other output devices. In particular, the present invention relates to a system and method for generating images with improved visual quality using local correlation, ordered dither.
2. Description of the Background Art
When an output device has a limited range of intensities, that range can be made to appear to be broader by half-toning the output on the output device. Half-toning is particularly useful when an output device has only two possible outputs for a pixel, white or opaque. A pixel is the smallest unit that the output device can resolve when rendered on a display device or paper. Examples of such limited range output devices are laser printers, ink jet printers, and liquid crystal displays. The output of such devices can be made to appear to have a gray scale, a range of grays between white and opaque, by half-toning. The theory underlying half-toning is that human visual perception tends to average closely adjacent pixels. Thus, by varying the density of white and opaque pixels, an image, that is made up entirely of white and opaque pixels, can be made to appear to have various levels of gray. Generally, the more opaque pixels in a region of an image, the darker gray is the appearance of the region.
There are two distinct and basic methods of half-toning. One method is error diffusion. In error diffusion, an error is calculated for each element of the input image. An element is a region of the input image that corresponds to a pixel of the output image. The error is the difference between the intensity of the element and the closest possible gray level. Once the errors have been calculated, a first element is selected. The error for the first pixel is used to adjust the intensity levels of adjacent elements. The adjacent elements are then selected and their errors are used to adjust the intensity levels of their adjacent elements. This process is repeated, and the error diffusion proceeds across the image. Once the errors are diffused, each pixel is assigned the gray level that is closest to the intensity level of its corresponding element.
Although it has a tendency to produce low frequency, texture artifacts, often called "worms," in the output image, error diffusion generally produces high quality output images. Error diffusion introduces noise to the output image. The frequency spectrum of the noise introduced by error diffusion appears as a cloud with no frequency, or frequencies, dominating. The noise spectrum of error diffusion is highly desirable. Error diffusion, however, is extremely computationally expensive. It is, therefore, slow and not the generally preferred method for dither.
The second, basic method for half-toning is called ordered dither. Ordered dither may be 2-dimensional or 3-dimensional. Two dimensional ordered dither involves a single dither matrix. A dither matrix, either for 2-dimensional or 3-dimensional dither, is typically 64 by 64 cells. The dither matrix is replicated, or tiled, across the image so that each element, and corresponding pixel, has a corresponding cell in a dither matrix.
Referring now to FIG. 1, a block diagram of 17 views of an exemplary dither matrix 10 providing 17 gray levels is shown. The exemplary dither matrix 10 comprises 16 cells. Each cell has an assigned threshold. Thus, a first cell 12 has threshold 1, a second cell 14 has threshold 2, and the remaining cells have thresholds such that a sixteenth cell 16 has threshold 16. A full sized dither matrix is generally much larger, such as 64 cells by 64 cells, and has thresholds between 1 and 4096, inclusive. A 16 cell by 16 cell matrix is being used here, however, for explanation purposes and ease of understanding. The thresholds would be appropriately scaled for the input signal. When an image is being half-toned, the intensity of each element of the input image is compared to the threshold of its corresponding cell. If the intensity of the element is greater than or equal to the threshold of the cell, then the corresponding pixel is turned on. When a pixel is turned "on" or "activated," it is made opaque. This method of ordered dither is often called fully stacked dither. In fully stacked dither pixel remains off until its threshold, held in the corresponding cell of a dither, a matrix, is reached by the intensity of the corresponding element in the input signal. Once a pixel is on, it is on for all higher intensities. This can be seen in FIG. 1. FIG. 1 shows the dither matrix 10 for all 17 gray levels that it can be used to produce. Note that the cells of the dither matrix 10 are not activated. FIG. 1 shows the pixels that would be activated, or turned on, for each gray level. Thus, the first view shows the cells activated by the lowest gray level; the second view shows the cells activated by the second lowest gray level, and the last view shows the cells activated by the highest gray level. A first gray level is all white, and no cells are turned on. The next gray level has the first cell 12 turned on. Therefore, if the element that corresponds to the first cell 12 has the first gray level, the corresponding pixel is turned on. If the elements that correspond to the other cells have the first gray level, then their corresponding pixels are not turned on. For each subsequent gray level, a cell has a matching threshold. Thus, for the third gray level, the second cell 14 has a threshold that would cause the corresponding pixel to be activated, and for the last gray level, all opaque, the sixteenth cell 16 and all other cells are activated.
FIG. 1 shows the dither matrix 10 for each of the 17 gray levels. Since the same dither matrix is used for all 17 gray levels, the dither matrix 10, full stacked dither is referred to as 2-dimensional dither.
This form of ordered dither is computationally inexpensive and is, therefor, generally preferred to error diffusion. It has, however, several deficiencies. A first deficiency is that the frequency spectrum of the noise introduced by fully stacked dither is not a cloud with no frequency, or frequencies, dominating. The frequency spectrum of the noise introduced by fully stacked dither has a few discrete frequencies dominating. It is unlike the cloud of noise introduced by error diffusion. A second deficiency is that one pattern of thresholds is optimal. A pattern is the layout of the thresholds within the dither matrix. The optimal pattern is generated for one gray level for the dither matrix. The optimal pattern is the pattern for a gray level that introduces the least distortion to the output. Additional thresholds are then added and subtracted for higher and lower gray levels, respectively. Only the initial pattern, however, is optimal. Additionally, as the gray level moves further away from the gray level having the initial, optimal pattern, the patterns may become less optimal.
These deficiencies in ordered dither have lead to attempts to develop dither techniques that produce noise frequency spectra that are more similar to the cloud of noise introduced by error diffusion. One of these techniques is 3-dimensional, gray level optimized ordered dither ("3DGLOOD"). 3DGLOOD attempts to overcome the problems of fully stacked dither and is often referred to as 3-dimensional dither. In 3DGLOOD, each gray level has a dither matrix, and a unique pattern of thresholds is generated for every gray level. The pattern of the thresholds of the dither matrix for a given gray level is optimized for that gray level. In 3-dimensional dither, the term pattern and the term dither matrix are often used interchangeably. Referring now to FIG. 2, a block diagram of an exemplary set 18 of dither matrices is shown. The set 18 of dither matrices having 17 dither matrices 20-52. Each dither matrix 20-52 is assigned to a gray level of a gray scale comprising 17 levels. Each dither matrix 20-52 comprises 16 cells arranged in a 4.times.4 square. The dither matrices 20-52 are assigned in order of the gray levels. Thus, the first dither matrix 20 is assigned to the first gray level, all off, and the last dither matrix 52 is assigned to the last gray level, all on. The intervening dither matrices 22-50 are assigned to the intervening gray levels. Each succeeding dither matrix 20-52 has one additional cell turned on. For example, the third dither matrix 24 has 2 cells turned on, and the fourth dither matrix 26 has 3 cells turned on. There are other ways the cells may be turned on; each succeeding gray level may have 2 cells turned on. This would require a 4.times.4 dither matrix to generate 9 gray levels.
For a selected element of an image, a dither matrix 20-52, which corresponds to the closest gray level to the intensity of the element, is selected. If the cell of the selected dither matrix, which corresponds with the element, is on, then the corresponding pixel is turned on, otherwise the pixel is turned off. This is not a threshold test. The cell indicates either to activate the corresponding pixel or not to activate the corresponding pixel.
For each dither matrix 20-52, the pattern of cells that are turned on is optimized for its assigned gray level. There is no relationship between the patterns of the dither matrices 20-52. Thus, 3DGLOOD eliminates the non-optimal pattern problem of fully stacked dither. 3DGLOOD, however, has an even greater problem. Each pattern of the dither matrices 20-52 is different. Human visual perception does not transition well between different patterns. Thus, when two adjacent gray levels are displayed next to each other, a viewer will perceive patterns in the output image. These patterns are due to changes in the frequency spectrum of neighboring gray level patterns. That is, 3DGLOOD does not produce a cloud of noise, but produces structure within the noise spectrum from the discontinuous matrices. These patterns are called visual artifacts and are introduced into the output image by 3DGLOOD. For this reason, 3DGLOOD is less preferred than fully stacked dither.
There is a need for a system and method for half-toning an image that is computationally inexpensive, that produces patterns that are close to optimal patterns, and that does not introduce visual artifacts into the output image.